package mine.code.question.动态规划;

import org.junit.Test;

/**
 * 给定一个长度为 n 的整数数组A。
 * <p>
 * 假设Bk是数组A顺时针旋转 k 个位置后的数组，我们定义A的“旋转函数”F为：
 * <p>
 * F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]。
 * <p>
 * 计算F(0), F(1), ..., F(n-1)中的最大值。
 * <p>
 * 注意:
 * 可以认为 n 的值小于 10^5。
 * <p>
 * 示例:
 * <p>
 * A = [4, 3, 2, 6]
 * <p>
 * F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
 * <p>
 * F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
 * <p>
 * F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
 * <p>
 * F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
 * <p>
 * 所以 F(0), F(1), F(2), F(3) 中的最大值是 F(3) = 26 。
 *
 * @author caijinnan
 */
public class 旋转函数 {


    @Test
    public void run() {
        int[] nums = {4, 3, 2, 6};
        System.out.println(maxRotateFunction(nums));
    }

    // 1,2 -> 0*1 + 1*2
    // 2,1 -> 0*2 + 1*1

    // 1,2,3 -> 0*1 + 1*2 + 2*3
    // 3,1,2 -> 0*3 + 1*1 + 2*2

    // 1,2,3,4 -> 0 + 1*2 + 2*3 + 3*4 = 20
    // 4,1,2,3 -> 0 + 1*1 + 2*2 + 3*3 = 14
    // 3,4,1,2 -> 0 + 1*4 + 2*1 + 3*2 = 12
    // 2,3,4,1 -> 0 + 1*3 + 2*4 + 3*1 = 14
    public int maxRotateFunction(int[] nums) {
        int length = nums.length;
        int numSum = 0;
        int multi = 0;
        int sum0 = 0;
        for (int num : nums) {
            sum0 += num * multi;
            numSum += num;
            multi++;
        }
        // subDp[i] = f(i)-f(i-1)
        // f(i)-f(i-1) = numSum - nums[(length-i+1)%length]-nums[(length-i)%length]+nums[(length-i+1)%length]-(n-1)*nums[(length-i)%length]
        // f(i) - f(i-1) = numSum - n*nums[(length-i)%length]
        int[] subDp = new int[length];
        subDp[0] = 0;
        int subSum = subDp[0];
        int maxSub = subDp[0];
        for (int i = 1; i < nums.length; i++) {
            subDp[i] = numSum - length * nums[(length - i) % length];
            subSum += subDp[i];
            maxSub = Math.max(maxSub, subSum);
        }
        return sum0 + maxSub;
    }
}
